package main

//#link: https://leetcode-cn.com/problems/number-of-submatrices-that-sum-to-target/
func main() {

}

func numSubmatrixSumTarget(matrix [][]int, target int) int {
	result := 0
	n, m := len(matrix), len(matrix[0])
	sum := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		sum[i] = make([]int, m+1)
	}
	for row := 1; row <= n; row++ {
		for col := 1; col <= m; col++ {
			sum[row][col] = sum[row-1][col] + sum[row][col-1] + matrix[row-1][col-1] - sum[row-1][col-1]
		}
	}
	//result = findTwoBridge(n, m, sum, target, result)
	for top := 1; top <= n; top++ {
		for bot := top; bot <= n; bot++ {
			tempMap := make(map[int]int)
			cur := 0
			for right := 1; right <= m; right++ {
				//计算下边界减去上边界的前缀和面积，即上下两边界间的距离
				cur = sum[bot][right] - sum[top-1][right]
				//计算得出的值与target相等则++
				if cur == target {
					result++
				}
				//查看是否有满足的左边界存在
				if value, ok := tempMap[cur-target]; ok {
					result += value
				}
				tempMap[cur]++
			}
		}
	}
	return result
}

/**
 * @Description: 寻找两个点
 */
func findTwoBridge(n int, m int, sum [][]int, target int, result int) int {
	//不断寻找两个点
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			for p := 1; p <= i; p++ {
				for q := 1; q <= j; q++ {
					if sum[i][j]-sum[p-1][j]-sum[i][q-1]+sum[p-1][q-1] == target {
						result++
					}
				}

			}
		}
	}
	return result
}
